This invention relates to the field of network analysis, and in particular to a method and system for assessing flows in a network that includes shared communications media.
As the demand for information flow continues to increase, establishing and maintaining an efficient network configuration to handle the increased flow typically requires complex analysis and planning. Generally, the analysis includes the identification of ‘bottlenecks’ where information flow is substantially impeded, or is expected to be impeded with future increases in traffic flow, and the planning includes the replacement or upgrading of equipment, or a reconfiguration of the network topology, to remove such bottlenecks, based on ‘what-if’ analyses of the benefits provided if such equipment or topology changes are made.
A common task for a network simulation system is “flow propagation analysis”, wherein the flow throughput is determined under a variety of traffic flow scenarios. For example, a nominal data flow of 10 Mbps bandwidth may exist between a source device and a destination device, but if some of the 10 Mbps bandwidth elements between the source and destination device are also providing communication paths between other sources and destinations, the effective throughput between the original source and destination device will be dependent upon the amount of bandwidth consumed by the traffic-flow among the other communication paths. If a particular router, for example, is common to multiple high-traffic communication paths, and does not have sufficient bandwidth to support these multiple traffic flows, it will force the high-traffic flows to be ‘throttled’ to a lower-than-maximum throughput. Flow-propagation-analysis provides an assessment of the effective bandwidth available to each traffic flow, assuming a given traffic profile.
U.S. Pat. No. 7,139,692, “FLOW PROPAGATION ANALYSIS USING ITERATIVE SIGNALING”, issued 21 Nov. 2006 to Alain Cohen, Pradeep Singh, Arun Pasupathy, Stefan Znam, and Marius Pops, teaches flow propagation analysis using ‘tracers’ that are iteratively propagated through a simulated network between source and destination elements, and is incorporated by reference herein. These tracers are structured to contain traffic flow information from source to destination, and to reflect changes as the flow is affected by each element along the path from source to destination. The resultant flow information at the destination corresponds to the effective throughput from the source to the destination, and the flow information at the output of each intermediate element in the network corresponds to the potentially achievable throughput through that element for the given source-to-destination flow.
Existing flow propagation analysis techniques such as taught in U.S. Pat. No. 7,139,692 effectively allocate the available bandwidth of each communication link among the traffic paths that use this link. The allocation is generally proportional to demand, although priority schemes may provide for a disproportioned allocation. For example, in a proportional allocation, if a given channel has a 12 MB maximum capacity, and is shared among three source-to-destination traffic paths with traffic demands of 3 MB, 6 MB, and 9 MB, the available 12 MB bandwidth would be allocated at this link to provide 2 MB, 4 MB, and 6 MB to these traffic flows, respectively. If the 3 MB traffic path had a higher priority than the others, it may receive its full demand of 3 MB, and the allocation to each of the others would be proportionately reduced. As each traffic flow is ‘throttled back’ at each over-loaded or over-subscribed link, its effective traffic demand at subsequent links is reduced, and consequently, its allocation of available bandwidth at subsequent links may be further reduced as it competes with other traffic flows at the subsequent links. The actual flow rate provided by the network to a given source-destination flow is the resultant flow rate on the last link to the destination, as this will reflect the result of each flow reduction at over-subscribed links.
Conventional flow propagation analysis techniques, however, have been found to be unsuitable for determining flows in networks that contain links with dynamic bandwidths, such as contention-based wireless links. As used herein, the term ‘bandwidth’ is used to indicate the realized bandwidth, i.e. the amount of actual traffic communicated per unit time, also termed the throughput of the link. As noted above, conventional flow propagation techniques operate by allocating the available bandwidth among traffic flows. If the available bandwidth is variable, a fixed allocation cannot be determined, and consequently the demand at subsequent links cannot be determined. Because the allocation at subsequent links is dependent upon the demand of each flow on the link, the allocations at all subsequent links along the path of traffic that flows through a dynamic-bandwidth link become indeterminable.
Compounding the problem further, the dynamic bandwidth of a contention based link is typically dependent upon the demand for the link in a non-linear manner, and, in a wireless communication system, the overall throughput of the link can be affected by traffic in neighboring links that share the same media.
Compounding the problem further still, in some cases, the link itself may be dynamic, such as links established among mobile devices. In addition to creating dynamic flow characteristics for the traffic on the dynamic link, these mobile devices may also dynamically become neighboring links to other links, thereby affecting the traffic flow on these other links as well.
Although dynamic bandwidth is a particularly acute problem in contention-based links, it should be noted that the aforementioned neighboring link and mobile link effects can also affect links that are typically consider fixed-bandwidth links. For example, a link with a reservation-based protocol generally exhibits fixed-bandwidth behavior. However, if this link shares the communication media with ‘distant’ devices that are not part of the reservation-based sub-network, the effective bandwidth will be dependent upon how far these devices are from devices in the sub-network, as well as the relative amount of traffic from the particular device that is close to these distant devices. For example, if the distance between a device on the sub-network and a distant device is such that the distant device is likely to interfere with 5% of the communications being received at the device on the sub-network, causing the sub-network to retransmit the communications, the resultant reduction in effective bandwidth on the sub-network is dependent upon the relative amount of traffic that is flowing to the affected device on the sub-network.
It would be advantageous to provide a flow propagation analysis technique that effectively and efficiently predicts flow characteristics in networks that include dynamic bandwidth links, such as contention-based links and other shared media communication links.
These advantages, and others, can be realized by a method and system wherein traffic flow at the OSI network layer is simulated at the traffic-flow level at interfaces to fixed bandwidth links, and simulated at the discrete-packet level at interfaces to dynamic bandwidth links. The resultant discrete-packet reception events at the receiving interface(s) of the dynamic bandwidth link are processed to determine the effective bandwidth/throughput of the link, as well as the allocation of this bandwidth among the individual flows through the link. The discrete-packet level receptions are used to reconstruct the parameters of the traffic flow at the network layer of the receiving interface, and this determined traffic flow is simulated accordingly at the next link, depending upon whether the next link is a static or dynamic bandwidth link.
Throughout the drawings, the same reference numerals indicate similar or corresponding features or functions. The drawings are included for illustrative purposes and are not intended to limit the scope of the invention.